package com.xiaomitest;

public class ZeroToOnePackage {
    /*
    #include <iostream>

    using namespace std;

    int w[105], val[105];
    int dp[105][1005];

    int main()
    {
        int t, m, res=-1;
        cin >> t >> m;
        for(int i=1; i<=m; i++)
            cin >> w[i] >> val[i];

        for(int i=1; i<=m; i++) //物品
            for(int j=t; j>=0; j--) //容量
            {
                if(j >= w[i])
                    dp[i][j] = max(dp[i-1][j-w[i]]+val[i], dp[i-1][j]);
                else      //只是为了好理解
                    dp[i][j] = dp[i-1][j];
            }
        cout << dp[m][t] << endl;
        return 0;
    }
    */

    /**
     * 由上面的图可以看出来，每一次V(i)(j)改变的值只与V(i-1)(x) {x:1...j}有关，V(i-1)(x)是前一次i循环保存下来的值；
     *
     * 　　因此，可以将V缩减成一维数组，从而达到优化空间的目的，状态转移方程转换为 B(j)= max{B(j), B(j-w(i))+v(i)}；
     *
     * 　　并且，状态转移方程，每一次推导V(i)(j)是通过V(i-1)(j-w(i))来推导的，所以一维数组中j的扫描顺序应该从大到小(capacity到0)，否则前一次循环保存下来的值将会被修改，从而造成错误。
     *
     */



    /*
    * //求解将哪些物品装入背包可使这些物品的重量总和不超过背包承重量t，且价值总和最大。
#include <stdio.h>
#include <string.h>

int f[1010],w[1010],v[1010];//f记录不同承重量背包的总价值，w记录不同物品的重量，v记录不同物品的价值

int max(int x,int y){//返回x,y的最大值
    if(x>y) return x;
    return y;
}

int main(){
    int t,m,i,j;
    memset(f,0,sizeof(f));  //总价值初始化为0
    scanf("%d %d",&t,&m);  //输入背包承重量t、物品的数目m
    for(i=1;i<=m;i++)
        scanf("%d %d",&w[i],&v[i]);  //输入m组物品的重量w[i]和价值v[i]
    for(i=1;i<=m;i++){  //尝试放置每一个物品
        for(j=t;j>=w[i];j--){//倒叙是为了保证每个物品都使用一次
            f[j]=max(f[j-w[i]]+v[i],f[j]);
            //在放入第i个物品前后，检验不同j承重量背包的总价值，如果放入第i个物品后比放入前的价值提高了，则修改j承重量背包的价值，否则不变
        }
    }
    printf("%d",f[t]);  //输出承重量为t的背包的总价值
    printf("\n");
    getch();
    return 0;
}
    * */
}
